'''
https://leetcode.cn/problems/longest-well-performing-interval/
'''
from typing import List


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        transfer = lambda x: 1 if x > 8 else -1
        nums = list(map(transfer, hours))
        dic = {0: -1}
        sum = 0
        ans = 0
        for i, num in enumerate(nums):
            sum += num
            if sum > 0:
                # 整体满足，最大肯定是目前整体
                ans = i + 1
            elif sum - 1 in dic:
                # 因为数组元素都是1,0,-1 。
                # 所以    1. -1 一定早于 -2 一定早于 -3;  先出现
                #        2. 如果有-(t+1)则一定有-t     出现过
                # 所以只需要找到前缀和为sum-1是的这段范围为1的位置j，然后看i~j 这段范围是否可行
                ans = max(ans, i - dic[sum - 1])
            # 只记录了，最早出现的位置
            if sum not in dic:
                dic[sum] = i
        return ans
